#ifndef BINARYSEARCHTREE_H_INCLUDED
#define BINARYSEARCHTREE_H_INCLUDED

#include "Vector.h"

namespace CEngine
{

template<class E, class K>
class PriorityQueue;

template<class Element, class Key = Element>
class BinarySearchTree {
    public:

        ///Internal node structure that the tree is made of.
        struct Node {
            Element element;
            Key key;

            U64 arrayPosition;

            Node* left;
            Node* right;

            Node(void)
                :   element(),
                    key(),
                    arrayPosition(0),
                    left(NULL),
                    right(NULL)
            {}
        };

        ///Creates an empty tree, relativeKey is false.
        BinarySearchTree(void);

        ///Creates a tree with element as the root, and relativeKey is set to true.
        ///key must be relative to element in some way (key is a
        BinarySearchTree(const Element& element, const Key& key);

        BinarySearchTree(const BinarySearchTree& tree);

        BinarySearchTree(Vector<Element>& vector, const Key& key);

        BinarySearchTree&
        operator= (const BinarySearchTree& tree);

        BinarySearchTree&
        operator= (Vector<Element>& vector);

        ~BinarySearchTree(void);

        Element&
        min(void) const;

        Element&
        current(void) const;

        Element&
        max(void) const;

        Element&
        operator[](const Key& key);

        Element&
        operator++(void);

        Element&
        operator--(void);

        void
        insert(const Element& element);

        void
        insert(const Element& element, const Key& key);

        void
        erase(void);

        void
        erase(const Key& key);

        void
        clear(void);

        bool
        isEmpty(void) const;

        U64
        getSize(void) const;

        Vector<Node>&
        getRawVector(void) const;

    private:

        Vector<Node> array;
        Node* root;
        U64 keyOffset;

        Node* currentKey;
        Vector<Node*> currentParentStack;

        Node* minKeyPointer;
        Node* maxKeyPointer;
        Key minKey;
        Key maxKey;

        bool relativeKey;

        void insertElement(const Key& key, const Element& element, Node& node);
        Node* findElement(const Key& key, Node* node, bool addToStack = true);

        friend PriorityQueue<Element, Key>;
};

}

#include "BinarySearchTreeCore.h"

#endif // BINARYSEARCHTREE_H_INCLUDED
